'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-08-13 16:09:40
LastEditTime: 2025-08-13 16:41:02
'''

# 从右往左找第一个“可以变大”的位置
# 在右边找到刚好比它大一点的数字
# 交换这两个数字
# 把交换位置右边的所有数字按升序排列

# 技巧，在找到之前一定是降序，找到之后翻转即可

class Solution:

    def nextPermutation(self, nums: list[int]) -> None:

        firstIndex = -1
        n = len(nums)

        def reverse(nums, i, j):
            # 翻转数组中的某一部分
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
        
        # 从倒数第二个数字开始
        for i in range(n-2, -1, -1):
            if nums[i] < nums[i+1]:
                firstIndex = i
                break
        
        if firstIndex == -1:
            reverse(nums, 0, n-1)
            return
        
        secondIndex = -1
        for i in range(n-1, firstIndex, -1):
            if nums[i] > nums[firstIndex]:
                secondIndex = i
                break
        
        nums[firstIndex], nums[secondIndex] = nums[secondIndex], nums[firstIndex]
        reverse(nums, firstIndex + 1, n - 1)


if __name__ == "__main__":

    a = [1, 2, 3]

    sol = Solution()
    print(a)
    sol.nextPermutation(a)
    print(a)
        



